定理1：
令$G$为一个阶数$n\geq 3$的图，如果对于任意整数$j$，满足$1\leq j < \frac{n}{2}$，$G$图中度数至多为$j$的节点个数少于$j$，那么图$G$是哈密顿图。
理解：
比较直观的理解一下就是，对于一个图，我们可以枚举$j$从$1$到$\frac{n}{2}$，比如度数至多为1的节点少于1个，度数至多为2的节点少于2个……
很容易发现，这是一个非常紧的定理，而且如果能够拿到所有节点的度的序列的话，完全可以在$O(n)$的时间复杂度下快速判断出一个图是否为哈密顿图。
前置定理：
定理：假设$u,v$是图$G$上的两个不相邻的点，但是满足$d(u)+d(v) \geq n$。那么图$G+uv$是哈密顿图当且仅当图$G$是哈密顿图。
证明：充分性是显然的。下面证明必要性：如果一个图$G+uv$是一个哈密顿图并且节点$u,v$是图上不相邻的两个点，然后图$G$不是一个哈密顿图。这意味着在图$G+uv$中的每一个哈密顿圈都需要经过$u-v$之间的路。所以$d(u) + d(v) \geq n$，$G$必然为哈密顿图，矛盾。
这意味着，我们在研究哈密顿性质是否存在的时候，可以先将图扩展到一个边数尽可能多的情况，因为他们是相互等价的。
一个图闭包(closure)的生成：
图$G$的闭包$C(G)$是：在图$G$中满足$d(u) + d(v) \geq n$且不相邻的一对节点$u,v$之间加入一条边，递归地重复上述过程，直到不存在满足要求的点对。
有关闭包的一些结论
定理：一个图的闭包是良定义的(按照不同的顺序递归生成结果一致)
定理：一个图是哈密顿图当且仅当它的闭包也是哈密顿图。
推论：一个阶数至少为3的图$G$，如果它的闭包$C(G)$是完全图，那么$G$是哈密顿图。
证明：
假设，该定理不成立。对于$C(G)$中的所有不相邻的节点，让$u,w$是一对度数和最大的节点。
显然$d_{C(G)}(u)+d_{C(G)}(v) \leq n-1$，我们不妨令u为度数较小的那个点。
令$d_{C(G)}(u) = j$，那么$j\leq \frac{n-1}{2}$，并且有$$d_{C(G)}(w) \leq n-j-1$$令$W$为所有不与$w$所相邻的点的集合，因此$u \in W$。观察到如果$v\in W$，那么就会有$d_{C(G)}(v)\leq j$，否则的话$$d_{C(G)}(v)+d_{C(G)}(w) > d_{C(G)}(u) + d_{C(G)}(w)$$这会导致与点$u$的定义相矛盾。
因此，集合$W$中每个节点的度数均至多为$j$。因为在假设中，$|W|\leq j-1$，因此
$$d_{C(G)}(w) \geq (n-1)-(j-1) = n-j$$ 矛盾！
